package com.weizu.mst;

import com.mengfou.sortUtils.ArraySort;
import com.mengfou.sortUtils.impl.ArraySortImpl;

import java.util.ArrayList;
import java.util.List;

public class T0808 {

    public static void main(String[] args) {
        int[] arr = new int[]{4, 6, 3, 2, 5, 4, 10, 4};

        new T0808().partitionThreePart(arr, 4);
        for (int i : arr) {
            System.out.print(i+"\t");
        }
        System.out.println();
    }

    /**
     * 划分数组数据为三部分
     * @param arr 待划分数组
     * @param num 划分值
     */
    private void partitionThreePart(int[] arr, int num) {
        int i = -1, j = arr.length - 1, k = 0;
        while(k < j){
            if(arr[k] < num) {  // 小于num的情况
                i++;
                swap(arr, i, k);
            }else if(arr[k] > num){ // 大于num的情况
                swap(arr, k, j);
                j--;
            } else{   // 等于num的情况
                k++;
            }
        }
    }

    /**
     * 异或运算进行交换两个数字
     * @param arr 数组
     * @param left 左边下标
     * @param right 右边下标
     */
    private void swap(int[] arr, int left, int right) {
        int temp = arr[left] ^ arr[right];
        arr[left] = temp ^ arr[left];
        arr[right] = arr[left] ^ temp;
    }
}
